package org.misty.practices.algorithm.step;

/*
有N级台阶，每次可以走1步或2步，共有多少种走法

n=1    1步                    f(1)=1

n=2    一次1步或直接2步         f(2)=2

n=3    先到达f(1)，然后跨2步    f(3)=f(1)+f(2)   设x=f(1)=1, y=f(2)=2
       先到达f(2)，然后跨1步    sum=f(3)= x + y

n=4    先到达f(2)，然后跨2步    f(4)=f(2)+f(3)   设x=f(2)=y', y=f(3)=sum'
       先到达f(3)，然后跨1步    sum=f(4)= x + y

...
n=k    先到达f(x-2)，然后跨2步   f(k)=f(k-2)+f(k-1)  设x=f(x-2)=y',y=f(x-1)=sum'
       先到达f(x-1)，然后跨1步   sum=f(k)= x + y
*/

/**
 * @author Misty on 2020-06-02
 */
public class StepsLoop {

    public static int step1(int n) {
        if (n == 1 || n == 2) return n;
        // n == 3
        int x = 1;
        int y = 2;
        int sum = x + y;
        if (n == 3) return sum;
        // n >= 4
        for (int i = 4; i <= n; i++) {
            x = y;  // 设 x = f(x-2) = y'
            y = sum; // 设 y = f(x-1) = sum'
            sum = x + y;
        }
        return sum;
    }

    public static int step(int n) {
        if (n == 1 || n == 2) return n;
        int x = 1, y = 2, sum = 0;
        for (int i = 3; i <= n; i++) {
            sum = x + y;
            x = y;
            y = sum;
        }
        return sum;
    }

    public static void main(String[] args) {
        long s = System.currentTimeMillis();
        for (int i = 0; i < 50000; i++) {
            step(10000);
        }
        long e = System.currentTimeMillis();
        System.out.println(e - s);
    }
}
